package LinkList;

import java.time.Year;

/**
 * 双向链表
 *
 * @author Delouch
 */

public class DoubleLinkList<E> {

    private DoubleLinkNode<E> head = null;

    private DoubleLinkNode<E> foot = null;

    private int size = 0;

    public void add(E element) {
        if (this.head == null) {
            this.head = new DoubleLinkNode(null, element, null);
            this.foot = this.head;
        }else  {
            DoubleLinkNode<E> node = new DoubleLinkNode(foot, element, null);
            DoubleLinkNode oldFoot = this.foot;
            oldFoot.nextNode = node;
            foot = node;
        }
        this.size += 1;
    }

    public void insert(E element, int index) {
        if (index == this.size) {
            add(element);
        }else {
            if (index == 0) {
                DoubleLinkNode<E> node = new DoubleLinkNode(null, element, this.head);
                this.head = node;
            }else {
                /// 找到上一个元素
                DoubleLinkNode preNode = findNode(index - 1);
                /// 插入元素的下一个元素
                DoubleLinkNode nextNode = preNode.nextNode;
                /// 创建插入元素
                DoubleLinkNode node = new DoubleLinkNode(preNode, element, preNode.nextNode);
                preNode.nextNode = node;
                nextNode.prevNode = node;
            }
            this.size += 1;
        }
    }

    public E removeLast() {
        if (this.foot == null) {
            return null;
        }
        DoubleLinkNode<E> oldFoot = foot;
        if (this.size == 1) {
            this.foot = null;
            this.head = null;
        }else  {
            this.foot = this.foot.prevNode;
            this.foot.nextNode = null;
        }
        this.size -= 1;
        return oldFoot.value;
    }

    public E removeFirst() {
        if (this.head == null) {
            return null;
        }
        DoubleLinkNode<E> oldHead = this.head;
        if (this.size == 1) {
            this.head = null;
            this.foot = null;
        }else {
            this.head = this.head.nextNode;
            this.head.prevNode = null;
        }
        this.size -= 1;
        return oldHead.value;
    }

    public E remove(int index) {
        if (index == 0) {
            return this.removeFirst();
        }
        if (index + 1 == this.size) {
            return this.removeLast();
        }
        DoubleLinkNode<E> node = null;
        /// 当前要删除的节点
        node = this.findNode(index);
        /// 要删除节点的上一个节点
        DoubleLinkNode preNode = node.prevNode;
        /// 上一个节点的下一个节点指向要删除节点的下一个节点
        preNode.nextNode = node.nextNode;
        /// 要删除节点的下一个节点的上一个节点，指向要删除节点的上一个节点
        node.nextNode.prevNode = preNode;
        this.size -= 1;
        return node.value;
    }

    private DoubleLinkNode<E> findNode(int index) {
        if (index >= this.size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size : " + this.size);
        }
        DoubleLinkNode<E> node = this.head;
        while (index > 0) {
            node = node.nextNode;
            index -= 1;
        }
        return node;
    }

    public E first() {
        if (this.head == null) {
            return null;
        }
        return this.head.value;
    }

    public E last() {
        if (this.foot == null) {
            return null;
        }
        return this.foot.value;
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0 ? true : false;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        DoubleLinkNode<E> node = head;
        while (node != null) {
            sb.append(node).append("  --  ");
            node = node.nextNode;
        }
        return sb.toString();
    }
}

class DoubleLinkNode<E> {

    E value;

    DoubleLinkNode nextNode;

    DoubleLinkNode prevNode;

    public DoubleLinkNode(DoubleLinkNode prevNode, E value, DoubleLinkNode nextNode) {
        this.value = value;
        this.nextNode = nextNode;
        this.prevNode = prevNode;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (prevNode == null) {
            sb.append("-");
        }else {
            sb.append(prevNode.value);
        }
        sb.append("  ").append(value).append("  ");
        if (nextNode == null) {
            sb.append("-");
        }else {
            sb.append(nextNode.value);
        }
        return sb.toString();
    }
}